package com.leetcode.array;

/**
 * 采用三路快拍的思路
 */
public class Leetcode75 {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int zero = -1 ; // [0...zero] == 0
        int two = n ; // [two...n-1] == 2
        int i = 0 ; // [zero+1 ... i] == 1
        while (i < two) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 0) {
                zero++;
                swap(nums, i, zero);
                i++;
            } else if (nums[i] == 2) {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {2,0,2,1,1,0};
        new Leetcode75().sortColors(arr);
        for (int i = 0 ; i < arr.length ; i++) {
            System.out.print(arr[i] + " ");
        }

    }

}
